// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-16 21:00
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.DataStruct.HashTable;

import org.junit.jupiter.api.Test;


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

@SuppressWarnings("ALL")
class AllOne {
    /**
     * 定义内部类节点实现双向链表
     */
    class Node {
        /**
         * 左右指针
         */
        Node left, right;
        // 当前链表中相同数量的字符串，存储在一个set中，使用set数据结构是为了避免出现相同的元素
        Set<String> set = new HashSet<>();
        // 当前节点的数量
        int cnt = 0;

        public Node(int cnt) {
            this.cnt = cnt;
        }
    }

    /**
     * Hash表，用于定位当前Strig在链表中的位置
     */
    Map<String, Node> map = new HashMap<>();
    Node hh, tt;

    /**
     * 保证所有操作的时间复杂度为O(1)
     * 节点构造器
     */
    public AllOne() {
        // 初始化双向链表，定义链表的头节点和尾节点
        hh = new Node(-1000);
        tt = new Node(-1000);
        hh.right = tt;
        tt.left = hh;
    }

    /**
     * 用于清楚双向链表中出现数量为0的节点
     * 一般用于删除节点时候把出现数量为0的的链表节点从当前双向链表中删除
     */
    void clear(Node node) {
        if (node.set.size() == 0) {
            node.left.right = node.right;
            node.right.left = node.left;
        }
    }

    /**
     * 插入节点 -> 1 节点已存在 2 节点不存在
     * 因为链表中的节点可以根据hash表在O(1)的时间复杂度下进行对位，所以双向链表的升序插入只需要O(1)的时间复杂度
     *
     * @param key 插入的String
     */
    public void inc(String key) {
        if (map.containsKey(key)) {
            // 链表中存在该节点 -> 节点cnt数量+1
            Node node = map.get(key);
            Node next = null;
            // 数据更新
            node.set.remove(key);
            // 移除节点之后需要清楚数量为空的节点
            if (node.right.cnt == node.cnt + 1) {
                // 因为当前节点数量增加了一个，而在双向链表中，当前节点的下一个节点刚好存储的是当前节点多一个节点数量的节点
                next = node.right;
            } else {
                // 没有节点存储cnt + 1 的String字符串节点
                // 创建新节点并且更改双向链表中的逻辑关系
                next = new Node(node.cnt + 1);
                next.left = node;
                next.right = node.right;
                node.right.left = next;
                node.right = next;
            }
            next.set.add(key);
            map.put(key, next);
            clear(node);
        } else {
            // 链表中不存在存储key的node节点
            if (hh.right.cnt == 1) {
                // 双向链表中第一个节点存储的是数量为1的node节点
                hh.right.set.add(key);
            } else {
                // 双向链表的第一个节点存储的数量不是1
                Node node = new Node(1);
                node.set.add(key);
                node.right = hh.right;
                hh.right.left = node;
                hh.right = node;
                node.left = hh;
            }
            map.put(key, hh.right);
        }
    }

    /**
     * @param key
     */
    public void dec(String key) {
        Node node = map.get(key);
        node.set.remove(key);
        Node prev = null;
        if (node.cnt == 1) {
            map.remove(key);
        } else {
            if (node.left.cnt == node.cnt - 1) {
                prev = node.left;
            } else {
                prev = new Node(node.cnt - 1);
                node.left.right = prev;
                prev.left = node.left;
                prev.right = node;
                node.left = prev;

            }
            prev.set.add(key);
            map.put(key, prev);
        }
        clear(node);
    }


    public String getMaxKey() {
        Node node = tt.left;
        for (String s : node.set) {
            return s;
        }
        return "";
    }

    public String getMinKey() {
        Node node = hh.right;
        for (String s : node.set) {
            return s;
        }
        return "";
    }


    @Test
    public void shout() {
        this.inc("a");
        this.inc("b");
        this.inc("b");
        this.inc("c");
        this.inc("c");
        this.inc("c");
        this.dec("b");
        this.dec("b");
        System.out.println(this.getMinKey());
        this.dec("a");
        System.out.println(this.getMaxKey());
        System.out.println(this.getMinKey());
    }


    @Test
    public void shout00() {
        this.inc("hello");
        this.inc("hello");
        System.out.println(this.getMaxKey());
        System.out.println(this.getMinKey());
        this.inc("leet");
        System.out.println(this.getMaxKey());
        System.out.println(this.getMinKey());
    }


}




/*
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */
